/*
    动态规划专题总结与预告

    【必备】阶段的动态规划专题
    从讲解066开始，到讲解088结束。一共23期视频，时长46小时，讲述117个题目

    动态规划基础，解决一旦有了尝试方法，怎么搞定后续的一整套实现：
    讲解066、067、068、069：一维、二维、三维动态规划，从递归开始到最终版本，包括空间压缩技巧

    高频动态规划问题：讲解070、071-子数组累加和问题与扩展    讲解072-最长递增子序列问题与扩展

    动态规划常见模型 & 尝试经验，核心在于怎么尝试？思路、经验太多了，如下都是经典尝试：
    讲解073、074、075-背包dp    讲解076、077-区间dp      讲解078、079-树型dp
    讲解080、081-状压dp         讲解084、085-数位dp

    动态规划常见技巧：
    讲解082、083-优化枚举       讲解086-获得具体方案      讲解087-根据数据量猜解法

    ================================================

    动态规划：https://oi-wiki.org/dp/
    一些递归有重复计算，可以用空间记录返回值来避免重复计算
    同时还有相关的一整套原理和技巧的总和

    什么样的递归可以变成动态规划？
    设计的可变参数类型简单，不比int类型更复杂的递归，可以变成动态规划
    如果递归过程中的路径信息比较复杂（回溯），那么不能或者没有必要改成动态规划，讲解067-题目2
    虽然有路径信息，但是路径信息比较简单的话，也可以改成动态规划，讲解080、081-状压dp

    重叠子结构
    最优子问题
    无后效性

    ================================================

    动态规划的大致过程：
    1，想出设计优良的递归尝试
    2，记忆化搜索(从顶到底的动态规划)
    3，严格位置依赖的动态规划(从底到顶的动态规划)
    4，进一步优化空间，也就是空间压缩
    5，进一步优化枚举行为

    尝试策略 = 转移方程

    推荐从尝试入手，最符合自然智慧
    进而分析位置依赖，分析位置依赖时多根据具体的例子画图，建立空间感
    动态规划方法的复杂度：O(状态数量 * 每个状态的枚举代价)
    尝试方法的优劣由题目具体的数据量决定，先确定靠谱尝试，然后再去做后续实现

    ================================================

    【必备】阶段已经讲过的动态规划优化的手段
    二进制分组、单调队列、滑动窗口：讲解075
    观察并优化转移方程、状态设计优化、高效查询结构(二分、预处理结构)：讲解082、讲解083、讲解087

    动态规划的优化手段，在后续的【扩展】、【挺难】课程中还会讲述：
    单调栈、树状数组、线段树、预处理结构（续）、状态设计优化（续）
    单调性优化（斜率优化、四边形不等式）
    等等

    同时还有以下内容和动态规划结合，也会在后续的【扩展】、【挺难】课程中讲述：
    树上倍增、换根dp、启发式合并、树上差分、轮廓线dp、容斥原理
    等等

    觉得好帮忙扩散吧！

*/